'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-09-08 23:32:19
'''
'''

77. 组合
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

这里的非递归版不是简单的用栈模拟递归转化为非递归：我们希望通过合适的手段，消除递归栈带来的额外空间代价。

假设我们把原序列中被选中的位置记为 1，不被选中的位置记为 0，对于每个方案都可以构造出一个二进制数。我们让原序列从大到小排列（即 \{ n, n - 1, \cdots 1, 0 \}{n,n−1,⋯1,0}）。我们先看一看 n = 4n=4，k = 2k=2 的例子：

我们可以看出「对应的二进制数」一列包含了由 k 个 1 和 n-k 个 0 组成的所有二进制数，并且按照字典序排列。这给了我们一些启发，我们可以通过某种方法枚举，使得生成的序列是根据字典序递增的。我们可以考虑我们一个二进制数数字 x，它由 k 个 1 和 n-k 个 0 组成，如何找到它的字典序中的下一个数字?

x 的最低位为 0(可以是0个)，这种情况下，末尾有 t 个连续的 0，而这 t 个连续的 0 之前有 m 个连续的 1，我们可以将倒数第 t+m 位置的 1 和倒数第 t+m+1 位的 0 对换，然后把倒数第 t+1 位到倒数第 t+m-1 位的 1 移动到最低位。

01001 -> 01010, 110011->110101, 001100->010001. 这些是在字典序里面紧密递增的。

再这个问题中，我们将k个数字{a0, ..., a(k-1)}初始位最小位置的1，则采用next规则，知道最大的1，遍历完毕。代码如下

'''
from typing import List
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        tmp = [i for i in range(1, k+1)]
        tmp.append(n+1) #哨兵，用于循环终止条件中。
        import copy
        while True:
            # i = 0
            ans.append(copy.copy(tmp[:-1]))
            i=0
            while i < k:
                if tmp[i]+1 != tmp[i+1]:
                    break
                i+=1
            if i==k: #与哨兵处对应
                break
            tmp[i] = tmp[i]+1
            for j in range(i):
                tmp[j]=j+1
        return ans
            
if __name__ == "__main__":
    solution = Solution()
    print(solution.combine(4, 2))